package offer.zixing.chapter15;

import java.util.*;

public class Test108 {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(ladderLength2("hit", "cog", list));
    }

    // 类似于 JVM 复制算法
    private static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue1 = new LinkedList<>();
        Queue<String> queue2 = new LinkedList<>();
        Set<String> notVisited = new HashSet<>(wordList);
        int length = 1;
        // 首元素初始化到队列中
        queue1.add(beginWord);
        while (!queue1.isEmpty()) {
            String word = queue1.poll();
            // 如果相同则说明已经找到，返回计数
            if (word.equals(endWord)) {
                return length;
            }
            List<String> neighbors = getNeighbors(word);
            for (String neighbor : neighbors) {
                // 单词列表中存在单词的演变
                if (notVisited.contains(neighbor)) {
                    // 存入第二个队列
                    queue2.add(neighbor);
                    // 单词列表移除
                    notVisited.remove(neighbor);
                }
            }
            // 队列一访问完，则说明演变一个轮回，length++
            if (queue1.isEmpty()) {
                length++;
                // 复制算法
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }

        }
        return 0;
    }

    // 双向广度优先搜索
    private static int ladderLength2(String beginWord, String endWord, List<String> wordList) {
        Set<String> notVisited = new HashSet<>(wordList);
        // 如果不包含则是 0
        if (!notVisited.contains(endWord)) {
            return 0;
        }
        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        // 包含开始到结束节点
        int length = 2;
        beginSet.add(beginWord);
        endSet.add(endWord);
        notVisited.remove(endWord);
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            // 优化查找，每次循环遍历较少的 set
            if (endSet.size() < beginSet.size()) {
                Set<String> temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }
            Set<String> set = new HashSet<>();
            for (String word : beginSet) {
                List<String> neighbors = getNeighbors(word);
                for (String neighbor : neighbors) {
                    if (endSet.contains(neighbor)) {
                        return length;
                    }
                    if (notVisited.contains(neighbor)) {
                        set.add(neighbor);
                        notVisited.remove(neighbor);
                    }
                }
            }
            length++;
            beginSet = set;
        }
        return 0;
    }

    /**
     * 获取单词只能改变一个字母后的单词列表
     *
     * @param  word
     * @return
     */
    private static List<String> getNeighbors(String word) {
        List<String> neighbors = new ArrayList<>();
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch != old) {
                    chars[i] = ch;
                    neighbors.add(new String(chars));
                }
            }
            chars[i] = old;
        }
        return neighbors;
    }
}
